Experiments with Game Tree Search in Real-Time Strategy Games

摘要

Game tree search algorithms such as minimax have been used with enormoussuccess in turn-based adversarial games such as Chess or Checkers. However,such algorithms cannot be directly applied to real-time strategy (RTS) gamesbecause a number of reasons. For example, minimax assumes a turn-taking gamemechanics, not present in RTS games. In this paper we present RTMM, a real-timevariant of the standard minimax algorithm, and discuss its applicability in thecontext of RTS games. We discuss its strengths and weaknesses, and evaluate itin two real-time games.